package tree.ordertraversal;

import tree.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Classname : ConstructBinaryTreeFromPreorderAndPostorderTraversal
 * @Description :
 * <a href="https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/">889. 根据前序和后序遍历构造二叉树</a>
 * @Author : chentianyu
 * @Date 2023/1/23 15:28
 */


public class ConstructBinaryTreeFromPreorderAndPostorderTraversal {

    /**
     * 思路：前序遍历用于重建树，后序遍历用于区分左右子树（通过获取右子树个数）
     *
     * @param preorder
     * @param postorder
     * @return
     */
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        Map<Integer, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < postorder.length; i++) indexMap.put(postorder[i], i);

        return constructFromPrePostHelper(preorder, indexMap, 0, preorder.length - 1);
    }

    private TreeNode constructFromPrePostHelper(int[] preorder, Map<Integer, Integer> indexMap, int preStart, int preEnd) {
        if (preStart > preEnd) return null;

        TreeNode root = new TreeNode(preorder[preStart]);
        //【题干条件】如果存在多个答案，您可以返回其中 任何一个 ==> 父节点只有一个节点，无论是左子节点还是右子节点其先序遍历和后序遍历一致，本题解默认为左子节点
        if (preStart < preEnd) {  // 至少存在一个子节点
            int postEnd = indexMap.get(preorder[preStart]);
            int index = indexMap.get(preorder[preStart + 1]);  // 后序遍历中当前节点左子节点的位置
            int rightSize = postEnd - 1 - index;  // 当前节点右子树节点个数

            root.left = constructFromPrePostHelper(preorder, indexMap, preStart + 1, preEnd - rightSize);
            root.right = constructFromPrePostHelper(preorder, indexMap, preEnd - rightSize + 1, preEnd);
        }
        return root;
    }
}
